package com.yww.leetcode.linkedlist;

import com.yww.leetcode.common.ListNode;

/**
 * @author yww
 * @description 141. 环形链表
 * @since 2024/2/3 15:33
 */
public class HasCycle141 {

    // 解：龟兔赛跑法，龟只走一步，兔走两步，如果兔子能追上龟说明存在环
    public boolean hasCycle(ListNode head) {
        if (head == null || head.next == null) {
            return false;
        }
        ListNode rabbit = head;
        ListNode turtle = head;
        while (rabbit != null && rabbit.next != null) {
            rabbit = rabbit.next.next;
            turtle = turtle.next;
            if (rabbit == turtle) {
                return true;
            }
        }
        return false;
    }
}
